﻿#include "SequenceLinke.h"
// C/C++ 学习网站：https://legacy.cplusplus.com 注意旧版本（搜索）和新版本

size_t add_size = 5; // 调整顺序表容量的增量

void seq_list_init(sqli* sl, size_t init_size)
{ // 初始化顺序表
	assert(sl); // 断言
	sl->data = NULL;
	sl->sz = 0;
	sl->capacity = init_size;  // 设置初始容量
	sl->data = (elem_type*)malloc(sl->capacity * sizeof(elem_type)); // 分配内存
	if (!sl->data) {
		perror("malloc failed");
		exit(1); // 内存分配失败，退出程序
	}
	printf("顺序表已初始化！\n");
}

void seq_list_destroy(sqli* sl)
{ // 销毁顺序表
	assert(sl); // 断言
	if (sl->data) {
		free(sl->data);
		sl->data = NULL;
	}
	sl->sz = 0;
	sl->capacity = 0;
	printf("顺序表已销毁！\n");
}

void show_index_elem(sqli* sl, int index)
{ // 显示指定顺序位置处的元素
	assert(sl && sl->data && sl->sz); // 断言
	if (index - 1 < 0 || index >= sl->sz) {
		printf("查找位置超出范围！\n");
		return;
	}
	printf("顺序位置 %d 的元素为：%d。\n", index, sl->data[index - 1]);
}

int search_elem(sqli* sl, elem_type elem)
{ // 查找元素，返回元素位置（从 1 开始）
	assert(sl); // 断言
	int i;
	for (i = 0; i < sl->sz; ++i)
		if (sl->data[i] == elem) {
			printf("在位置 %d 找到元素 %d \n", i + 1, elem);
			return i + 1;
		}
	printf("元素 %d 不存在！\n", elem);
	return -1;
}

void show_all_elem(sqli* sl)
{ // 显示所有元素
	assert(sl); // 断言
	printf("顺序表中共有 %d 个元素；所有元素如下：\n", sl->sz);
	int i;
	for (i = 0; i < sl->sz; i++)
		printf("%d ", sl->data[i]);
	printf("\n");
}

static void seq_list_resize(sqli* sl, size_t cmp_sz)
{ // 动态调整顺序表容量，增加 add_size 容量，用于容纳新元素
	assert(sl); // 断言
	if (add_size <= 0)
		return; // 容量小于等于 0，不调整
	else if (sl->capacity > cmp_sz)
		return; // 容量大于等于元素个数，不调整
	else
	{
		elem_type* new_data =
			(elem_type*)realloc(sl->data, (add_size + sl->capacity) * sizeof(elem_type));
		if (!new_data) {
			perror("realloc failed");
			return;
		}
		sl->data = new_data;
		new_data = NULL; // 释放临时指针
		sl->capacity += add_size;
	}
	printf("顺序表容量已调整！当前容量为：%d；现有元素个数为：%d。\n", sl->capacity, sl->sz);
}

void add_elem_end(sqli* sl, elem_type elem)
{ // 向顺序表尾部添加元素
	assert(sl); // 断言
	seq_list_resize(sl, sl->sz); // 调整容量
	sl->data[sl->sz++] = elem; // 添加元素
	//printf("元素已添加到顺序表尾部！\n");
}

elem_type del_elem_end(sqli* sl)
{ // 删除顺序表尾部元素，返回被删除的元素
	assert(sl); // 断言
	if (sl->sz == 0) {
		printf("顺序表为空！\n");
		return;
	}
	elem_type ret = sl->data[sl->sz - 1]; // 保存被删除的元素
	sl->data[sl->sz - 1] = 0; // 清空元素
	--sl->sz; // 元素个数减 1
	return ret; // 返回被删除的元素
	//printf("元素已从顺序表尾部删除！\n");
}

void add_elem_head(sqli* sl, elem_type elem)
{ // 向顺序表头部添加元素
	assert(sl); // 断言
	++sl->sz; // 元素个数加 1 
	seq_list_resize(sl, sl->sz); // 判断是否能容纳新元素，若不能则调整容量
	int i;
	for (i = sl->sz - 1; i > 0; --i)
		sl->data[i] = sl->data[i - 1];
	sl->data[0] = elem; // 添加元素
	//printf("元素已添加到顺序表头部！\n");
}

elem_type del_elem_head(sqli* sl)
{ // 删除顺序表头部元素，返回被删除的元素
	assert(sl); // 断言
	if (sl->sz == 0) {
		printf("顺序表为空！\n");
		return;
	}
	elem_type ret = sl->data[0]; // 保存被删除的元素
	int i;
	for (i = 0; i < sl->sz - 1; ++i)
		sl->data[i] = sl->data[i + 1];
	sl->data[sl->sz - 1] = 0; // 清空最后一个元素
	--sl->sz; // 元素个数减 1
	return ret; // 返回被删除的元素
	//printf("元素已从顺序表头部删除！\n");
}

void insert_index_elem(sqli* sl, int index, int value)
{ // 插入元素到指定位置
	assert(sl); // 断言
	if (index < 1 || index > sl->sz) {
		printf("插入位置超出范围！\n");
		return;
	}
	++sl->sz; // 元素个数加 1
	seq_list_resize(sl, sl->sz); // 判断是否能容纳新元素，若不能则调整容量
	int i;
	for (i = sl->sz - 1; i > index - 1; --i)
		sl->data[i] = sl->data[i - 1];
	sl->data[index - 1] = value; // 插入元素
	//printf("元素已插入到指定位置！\n");
}

int del_elem(sqli* sl, elem_type elem)
{ // 删除指定的元素，返回被删除元素的位置
	assert(sl); // 断言
	if (sl->sz == 0) {
		printf("顺序表为空！\n");
		return -1;
	}
	int i, j;
	for (i = 0; i < sl->sz; ++i)
		if (sl->data[i] == elem)
		{
			for (j = i; j < sl->sz - 1; ++j)
				sl->data[j] = sl->data[j + 1];
			sl->data[sl->sz - 1] = 0; // 清空最后一个元素
			--sl->sz; // 元素个数减 1
			return i + 1; // 返回被删除的元素
		}
	printf("元素 %d 不存在！\n", elem);
	return -1; // 未找到元素
}

elem_type del_index_elem(sqli* sl, int index)
{ // 删除指定位置的元素，返回被删除元素的值
	assert(sl && sl->data && sl->sz); // 断言
	if (index < 1 || index > sl->sz) {
		printf("删除位置超出范围！\n");
		return;
	}
	elem_type ret = sl->data[index - 1]; // 保存被删除的元素
	int i;
	for (i = index - 1; i < sl->sz - 1; ++i)
		sl->data[i] = sl->data[i + 1];
	sl->data[sl->sz - 1] = 0; // 清空最后一个元素
	--sl->sz; // 元素个数减 1
	return ret; // 返回被删除的元素
	//printf("元素已从指定位置删除！\n");
}

void modify_index_elem(sqli* sl, int index, elem_type value)
{ // 修改指定位置的元素的值
	assert(sl && sl->data && sl->sz); // 断言
	if (index < 1 || index > sl->sz) {
		printf("修改位置超出范围！\n");
		return;
	}
	sl->data[index - 1] = value; // 修改元素的值
	//printf("元素已修改！\n");
}

void merge_seq_list(sqli* sl1, sqli* sl2)
{ // 合并两个顺序表
	assert(sl1 && sl2); // 断言
	int sz2 = sl2->sz;
	while (sl1->sz + sz2 > sl1->capacity) // 判断是否能容纳新元素，若不能则调整容量
		seq_list_resize(sl1, sl1->sz + sz2);
	elem_type* in_data = (elem_type*)malloc(sl2->sz * sizeof(elem_type));
	// 分配内存，储存 sl2 的元素 data
	if (!in_data) {
		perror("malloc failed");
		return;
	}
	in_data = sl2->data; // 保存 sl2 的元素 data
	int i;
	for (i = 0; i < sz2; ++i)
		sl1->data[sl1->sz++] = in_data[i]; // 合并 sl2 的元素到 sl1
	in_data = NULL; // 释放内存
	//printf("两个顺序表已合并！\n");
}

void reverse_seq_list(sqli* sl)
{ // 反转顺序表
	assert(sl && sl->data && sl->sz); // 断言
	int i, j;
	elem_type temp;
	for (i = 0, j = sl->sz - 1; i < j; ++i, --j)
	{
		temp = sl->data[i];
		sl->data[i] = sl->data[j];
		sl->data[j] = temp;
	}
	//printf("顺序表已反转！\n");
}

static void quick_sort_elem(elem_type* data, int left, int right)
{ // 快速排序算法，升序排序，left 和 right 不能是 size_t，否则会溢出（因为left可能为 -1）
	if (left >= right)
		return; // 已排序完成
	int start = left, end = right; // 保存扫描区间起始位置
	elem_type pivot = data[left]; // 选取第一个元素作为基准
	while (left < right)
	{
		while (left < right && data[right] >= pivot) // 从左向右扫描，找到一个大于基准的元素
			--right;
		data[left] = data[right]; // 交换元素
		while (left < right && data[left] <= pivot) // 从右向左扫描，找到一个小于基准的元素
			++left;
		data[right] = data[left]; // 交换元素
	}
	data[left] = pivot; // 基准元素归位
	quick_sort_elem(data, start, left - 1); // 递归左半区间
	quick_sort_elem(data, right + 1, end); // 递归右半区间
}

static int cmp_elem_upper(const void* a, const void* b)
{ // 用于 qsort() 排序的比较函数
	return (*(elem_type*)a - *(elem_type*)b); // 升序排序
}

static int cmp_elem_lower(const void* a, const void* b)
{ // 用于 qsort() 排序的比较函数
	return (*(elem_type*)a - *(elem_type*)b); // 升序排序
}

void sort_seq_list(sqli* sl)
{ // 排序顺序表，使用快速排序算法
	assert(sl && sl->data && sl->sz); // 断言
	if (sl->sz == 1)
		return; // 只有一个元素，无需排序
	quick_sort_elem(sl->data, 0, sl->sz - 1);
	// 可以使用库函数 qsort() 排序，示例如下：
	//qsort(sl->data, sl->sz, sizeof(elem_type), cmp_elem_upper);
	//printf("顺序表已排序！\n");
}

size_t get_seq_list_len(sqli* sl)
{ // 获取顺序表的元素个数
	assert(sl); // 断言
	return sl->sz;
}